

inline size_t Parent(size_t x,size_t d=2)
{
	return (x+(d-2))/d;
}

inline size_t Left(size_t x,size_t d=2)
{
	return d*x-(d-2);
}

inline size_t Right(size_t x, size_t d=2)
{
	return d*x+1;
}

template<typename T,size_t d>
void MaxHeapifyDArr(T *vec, size_t cnt, size_t pos)
{
	size_t l=Left(pos);
	size_t r=Right(pos);
	size_t largest=pos;
	for(size_t i=l;i<=r && i<cnt;++i)
	{
		if(vec[i]>vec[largest])
			largest=i;
	}
	if(largest != pos)
	{
		T temp=vec[pos];
		vec[pos]=vec[largest];
		vec[largest]=temp;
		MaxHeapifyDArr<T,d>(vec,cnt,largest);
	}
}

template<typename T,size_t d>
void BuildMaxHeapDArr(T *vec, size_t cnt)
{
	size_t endPos=Parent(cnt,d);
	for(size_t i = 0 ;i <=endPos; ++i)
	{
		MaxHeapifyDArr<T,d>(vec,cnt,i);
	}
}

template<typename T,size_t d>
void HeapSortDArr(T *vec, size_t cnt)
{
	BuildMaxHeapDArr<T,d>(vec,cnt);
	for(size_t i = cnt; i>=2;)
	{
		T temp=vec[i-1];
		vec[i-1]=vec[0];
		vec[0]=temp;
		MaxHeapifyDArr<T,d>(vec,--i,0);
	}
}